home *** CD-ROM | disk | FTP | other *** search
/ T&A 2 the Maxx 3 / T and A 2 The Maxx Number 3.iso / viewers / unixview / xgiftar.z / xgiftar / reduce.c < prev    next >
C/C++ Source or Header  |  1991-05-20  |  16KB  |  626 lines
  1. /* reduce.c:
  2.  *
  3.  * reduce an image's colormap usage to a set number of colors.  this also
  4.  * translates a true color image to a TLA-style image of `n' colors.
  5.  *
  6.  * this uses an algorithm by Paul Heckbert discussed in `Color Image
  7.  * Quantization for Frame Buffer Display,' _Computer Graphics_ 16(3),
  8.  * pp 297-307.  this implementation is based on one discussed in
  9.  * 'A Few Good Colors,' _Computer Language_, Aug. 1990, pp 32-41 by
  10.  * Dave Pomerantz.
  11.  *
  12.  * this function cannot reduce to any number of colors larger than 32768.
  13.  *
  14.  * jim frost 04.18.91
  15.  *
  16.  * Copyright 1991 Jim Frost.
  17.  * See included file "copyright.h" for complete copyright information.
  18.  */
  19.  
  20. #include "copyright.h"
  21. #include "image.h"
  22.  
  23. #define DIST(A, B) ((A) < (B) ? (B) - (A) : (A) - (B))
  24.  
  25. /* find the distance between two colors.  we loose some accuracy here because
  26.  * a triple squared short may not fit in a long.  we use a table lookup
  27.  * to help speed this up; it's an O(exp(n,2)) algorithm.
  28.  */
  29.  
  30. unsigned int  squareInit= 0;
  31. unsigned long squareTable[32768];
  32.  
  33. void initSquareTable()
  34. { unsigned long a;
  35.  
  36.   for (a= 0; a < 32768; a++)
  37.     squareTable[a]= a * a;
  38.   squareInit= 1;
  39. }
  40.  
  41. unsigned long colorDistance(rgb, a, b)
  42.      RGBMap *rgb;
  43.      Pixel   a, b;
  44. {
  45.   return(squareTable[DIST(*(rgb->red + a), *(rgb->red + b)) >> 1] +
  46.      squareTable[DIST(*(rgb->green + a), *(rgb->green + b)) >> 1] +
  47.      squareTable[DIST(*(rgb->blue + a), *(rgb->blue + b)) >> 1]);
  48. }
  49.  
  50. /* this converts a TLA-style pixel into a 15-bit true color pixel
  51.  */
  52.  
  53. #define TLA_TO_15BIT(TABLE,PIXEL)           \
  54.   ((((TABLE).red[PIXEL] & 0xf800) >> 1) |   \
  55.    (((TABLE).green[PIXEL] & 0xf800) >> 6) | \
  56.    (((TABLE).blue[PIXEL] & 0xf800) >> 11))
  57.  
  58. /* this converts a 24-bit true color pixel into a 15-bit true color pixel
  59.  */
  60.  
  61. #define TRUE_TO_15BIT(PIXEL)     \
  62.   ((((PIXEL) & 0xf80000) >> 9) | \
  63.    (((PIXEL) & 0x00f800) >> 6) | \
  64.    (((PIXEL) & 0x0000f8) >> 3))
  65.  
  66. /* these macros extract color intensities from a 15-bit true color pixel
  67.  */
  68.  
  69. #define RED_INTENSITY(P)   (((P) & 0x7c00) >> 10)
  70. #define GREEN_INTENSITY(P) (((P) & 0x03e0) >> 5)
  71. #define BLUE_INTENSITY(P)   ((P) & 0x001f)
  72.  
  73. /* this structure defines a color area which is made up of an array of pixel
  74.  * values and a count of the total number of image pixels represented by
  75.  * the area.  color areas are kept in a list sorted by the number of image
  76.  * pixels they represent.
  77.  */
  78.  
  79. struct color_area {
  80.     unsigned short    *pixels;       /* array of pixel values in this area */
  81.     unsigned short     num_pixels;   /* size of above array */
  82.     int              (*sort_func)(); /* predicate func to sort with before
  83.                       * splitting */
  84.     unsigned long      pixel_count;  /* # of image pixels we represent */
  85.     struct color_area *prev, *next;
  86. };
  87.  
  88. /* predicate functions for qsort
  89.  */
  90.  
  91. static sortRGB(p1, p2)
  92.      unsigned short *p1, *p2;
  93. { unsigned int red1, green1, blue1, red2, green2, blue2;
  94.  
  95.   red1= RED_INTENSITY(*p1);
  96.   green1= GREEN_INTENSITY(*p1);
  97.   blue1= BLUE_INTENSITY(*p1);
  98.   red2= RED_INTENSITY(*p2);
  99.   green2= GREEN_INTENSITY(*p2);
  100.   blue2= BLUE_INTENSITY(*p2);
  101.  
  102.   if (red1 == red2)
  103.     if (green1 == green2)
  104.       if (blue1 < blue2)
  105.     return(-1);
  106.       else
  107.     return(1);
  108.     else if (green1 < green2)
  109.       return(-1);
  110.     else
  111.       return(1);
  112.   else if (red1 < red2)
  113.     return(-1);
  114.   else
  115.     return(1);
  116. }
  117.  
  118. static sortRBG(p1, p2)
  119.      unsigned short *p1, *p2;
  120. { unsigned int red1, green1, blue1, red2, green2, blue2;
  121.  
  122.   red1= RED_INTENSITY(*p1);
  123.   green1= GREEN_INTENSITY(*p1);
  124.   blue1= BLUE_INTENSITY(*p1);
  125.   red2= RED_INTENSITY(*p2);
  126.   green2= GREEN_INTENSITY(*p2);
  127.   blue2= BLUE_INTENSITY(*p2);
  128.  
  129.   if (red1 == red2)
  130.     if (blue1 == blue2)
  131.       if (green1 < green2)
  132.     return(-1);
  133.       else
  134.     return(1);
  135.     else if (blue1 < blue2)
  136.       return(-1);
  137.     else
  138.       return(1);
  139.   else if (red1 < red2)
  140.     return(-1);
  141.   else
  142.     return(1);
  143. }
  144.  
  145. static sortGRB(p1, p2)
  146.      unsigned short *p1, *p2;
  147. { unsigned int red1, green1, blue1, red2, green2, blue2;
  148.  
  149.   red1= RED_INTENSITY(*p1);
  150.   green1= GREEN_INTENSITY(*p1);
  151.   blue1= BLUE_INTENSITY(*p1);
  152.   red2= RED_INTENSITY(*p2);
  153.   green2= GREEN_INTENSITY(*p2);
  154.   blue2= BLUE_INTENSITY(*p2);
  155.  
  156.   if (green1 == green2)
  157.     if (red1 == red2)
  158.       if (blue1 < blue2)
  159.     return(-1);
  160.       else
  161.     return(1);
  162.     else if (red1 < red2)
  163.       return(-1);
  164.     else
  165.       return(1);
  166.   else if (green1 < green2)
  167.     return(-1);
  168.   else
  169.     return(1);
  170. }
  171.  
  172. static sortGBR(p1, p2)
  173.      unsigned short *p1, *p2;
  174. { unsigned int red1, green1, blue1, red2, green2, blue2;
  175.  
  176.   red1= RED_INTENSITY(*p1);
  177.   green1= GREEN_INTENSITY(*p1);
  178.   blue1= BLUE_INTENSITY(*p1);
  179.   red2= RED_INTENSITY(*p2);
  180.   green2= GREEN_INTENSITY(*p2);
  181.   blue2= BLUE_INTENSITY(*p2);
  182.  
  183.   if (green1 == green2)
  184.     if (blue1 == blue2)
  185.       if (red1 < red2)
  186.     return(-1);
  187.       else
  188.     return(1);
  189.     else if (blue1 < blue2)
  190.       return(-1);
  191.     else
  192.       return(1);
  193.   else if (green1 < green2)
  194.     return(-1);
  195.   else
  196.     return(1);
  197. }
  198.  
  199. static sortBRG(p1, p2)
  200.      unsigned short *p1, *p2;
  201. { unsigned int red1, green1, blue1, red2, green2, blue2;
  202.  
  203.   red1= RED_INTENSITY(*p1);
  204.   green1= GREEN_INTENSITY(*p1);
  205.   blue1= BLUE_INTENSITY(*p1);
  206.   red2= RED_INTENSITY(*p2);
  207.   green2= GREEN_INTENSITY(*p2);
  208.   blue2= BLUE_INTENSITY(*p2);
  209.  
  210.   if (blue1 == blue2)
  211.     if (red1 == red2)
  212.       if (green1 < green2)
  213.     return(-1);
  214.       else
  215.     return(1);
  216.     else if (red1 < red2)
  217.       return(-1);
  218.     else
  219.       return(1);
  220.   else if (blue1 < blue2)
  221.     return(-1);
  222.   else
  223.     return(1);
  224. }
  225.  
  226. static sortBGR(p1, p2)
  227.      unsigned short *p1, *p2;
  228. { unsigned int red1, green1, blue1, red2, green2, blue2;
  229.  
  230.   red1= RED_INTENSITY(*p1);
  231.   green1= GREEN_INTENSITY(*p1);
  232.   blue1= BLUE_INTENSITY(*p1);
  233.   red2= RED_INTENSITY(*p2);
  234.   green2= GREEN_INTENSITY(*p2);
  235.   blue2= BLUE_INTENSITY(*p2);
  236.  
  237.   if (blue1 == blue2)
  238.     if (green1 == green2)
  239.       if (red1 < red2)
  240.     return(-1);
  241.       else
  242.     return(1);
  243.     else if (green1 < green2)
  244.       return(-1);
  245.     else
  246.       return(1);
  247.   else if (blue1 < blue2)
  248.     return(-1);
  249.   else
  250.     return(1);
  251. }
  252.  
  253. /* this does calculations on a color area following a split and inserts
  254.  * the color area in the list of color areas.
  255.  */
  256.  
  257. static insertColorArea(pixel_counts, rlargest, rsmallest, area)
  258.      unsigned long *pixel_counts;
  259.      struct color_area **rlargest, **rsmallest, *area;
  260. { int a;
  261.   unsigned int red, green, blue;
  262.   unsigned int min_red, min_green, min_blue;
  263.   unsigned int max_red, max_green, max_blue= 0;
  264.   struct color_area *largest, *smallest, *tmp_area;
  265.  
  266.   min_red= min_green= min_blue= 31;
  267.   max_red= max_green= max_blue= 0;
  268.  
  269.   /* update pixel count for this area and find RGB intensity widths
  270.    */
  271.  
  272.   area->pixel_count= 0;
  273.   for (a= 0; a < area->num_pixels; a++) {
  274.     area->pixel_count += pixel_counts[area->pixels[a]];
  275.     red= RED_INTENSITY(area->pixels[a]);
  276.     green= GREEN_INTENSITY(area->pixels[a]);
  277.     blue= BLUE_INTENSITY(area->pixels[a]);
  278.     if (red < min_red)
  279.       min_red= red;
  280.     if (red > max_red)
  281.       max_red= red;
  282.     if (green < min_green)
  283.       min_green= green;
  284.     if (green > max_green)
  285.       max_green= green;
  286.     if (blue < min_blue)
  287.       min_blue= blue;
  288.     if (blue > max_blue)
  289.       max_blue= blue;
  290.   }
  291.  
  292.   /* calculate widths and determine which predicate function to use based
  293.    * on the result
  294.    */
  295.  
  296.   red= max_red - min_red;
  297.   green= max_green - min_green;
  298.   blue= max_blue - min_blue;
  299.  
  300.   if (red > green)
  301.     if (green > blue)
  302.       area->sort_func= sortRGB;
  303.     else if (red > blue)
  304.       area->sort_func= sortRBG;
  305.     else
  306.       area->sort_func= sortBRG;
  307.   else if (green > blue)
  308.     if (red > blue)
  309.       area->sort_func= sortGRB;
  310.     else
  311.       area->sort_func= sortGBR;
  312.   else
  313.     area->sort_func= sortBGR;
  314.  
  315.   /* insert color area in color area list sorted by number of pixels that
  316.    * the area represents
  317.    */
  318.  
  319.   largest= *rlargest;
  320.   smallest= *rsmallest;
  321.  
  322.   if (!largest) {
  323.     largest= smallest= area;
  324.     area->prev= area->next= (struct color_area *)NULL;
  325.   }
  326.  
  327.   /* if we only have one element, our pixel count is immaterial so we get
  328.    * stuck on the end of the list.
  329.    */
  330.  
  331.   else if (area->num_pixels < 2) {
  332.     smallest->next= area;
  333.     area->prev= smallest;
  334.     area->next= (struct color_area *)NULL;
  335.     smallest= area;
  336.   }
  337.  
  338.   /* insert node into list
  339.    */
  340.  
  341.   else {
  342.     for (tmp_area= largest; tmp_area; tmp_area= tmp_area->next)
  343.       if ((area->pixel_count > tmp_area->pixel_count) ||
  344.       (tmp_area->num_pixels < 2)) {
  345.     area->prev= tmp_area->prev;
  346.     area->next= tmp_area;
  347.     tmp_area->prev= area;
  348.     if (area->prev)
  349.       area->prev->next= area;
  350.     else
  351.       largest= area;
  352.     break;
  353.       }
  354.     if (!tmp_area) {
  355.       area->prev= smallest;
  356.       area->next= (struct color_area *)NULL;
  357.       smallest->next= area;
  358.       smallest= area;
  359.     }
  360.   }
  361.   *rlargest= largest;
  362.   *rsmallest= smallest;
  363. }
  364.  
  365. Image *reduce(image, n, verbose)
  366.      Image *image;
  367.      unsigned int n, verbose;
  368. { unsigned long pixel_counts[32768]; /* pixel occurrance histogram */
  369.   unsigned short pixel_array[32768];
  370.   unsigned long count, midpoint;
  371.   int x, y, num_pixels, allocated, depth, ncolors;
  372.   byte *pixel, *dpixel;
  373.   struct color_area *areas, *largest_area, *smallest_area;
  374.   struct color_area *new_area, *old_area;
  375.   Image *new_image;
  376.   char buf[BUFSIZ];
  377.  
  378.   goodImage(image, "reduce");
  379.   if (n > 32768) /* max # of colors we can handle */
  380.     n= 32768;
  381.  
  382.   /* create a histogram of particular pixel occurrances
  383.    */
  384.  
  385.   bzero(pixel_counts, 32768 * sizeof(unsigned long));
  386.   switch (image->type) {
  387.   case IBITMAP:
  388.       return(image);
  389.  
  390.   case IRGB:
  391.     if (image->rgb.used <= n)
  392.       return;
  393.     if (verbose) {
  394.       printf("  Reducing RGB image color usage to %d colors...", n);
  395.       fflush(stdout);
  396.     }
  397.     pixel= image->data;
  398.     for (y= 0; y < image->height; y++)
  399.       for (x= 0; x < image->width; x++) {
  400.     pixel_counts[TLA_TO_15BIT(image->rgb,
  401.                   memToVal(pixel, image->pixlen))]++;
  402.     pixel += image->pixlen;
  403.       }
  404.     break;
  405.  
  406.   case ITRUE:
  407.     if (image->pixlen != 3) {
  408.       fprintf(stderr, "reduce: true color image has strange pixel length?\n");
  409.       return(image);
  410.     }
  411.     if (verbose) {
  412.       printf("  Converting true color image to RGB image with %d colors...",
  413.          n);
  414.       fflush(stdout);
  415.     }
  416.  
  417.     pixel= image->data;
  418.     for (y= 0; y < image->height; y++)
  419.       for (x= 0; x < image->width; x++) {
  420.     pixel_counts[TRUE_TO_15BIT(memToVal(pixel, 3))]++;
  421.     pixel += 3;
  422.       }
  423.     break;
  424.  
  425.   default:
  426.       return(image); /* not something we can reduce, thank you anyway */
  427.   }
  428.  
  429.   /* create array of 15-bit pixel values that actually occur in the image
  430.    */
  431.  
  432.   num_pixels= 0;
  433.   for (x= 0; x < 32768; x++)
  434.     if (pixel_counts[x] > 0)
  435.       pixel_array[num_pixels++]= (short)x;
  436.   if (verbose) {
  437.     printf("image uses %d colors...", num_pixels);
  438.     fflush(stdout);
  439.   }
  440.  
  441.   /* create color area array and initialize first element
  442.    */
  443.  
  444.   areas= (struct color_area *)lmalloc(n * sizeof(struct color_area));
  445.   areas[0].pixels= pixel_array;
  446.   areas[0].num_pixels= num_pixels;
  447.   largest_area= smallest_area= (struct color_area *)NULL;
  448.   insertColorArea(pixel_counts, &largest_area, &smallest_area, areas);
  449.   allocated= 1;
  450.  
  451.   /* keep splitting the color area until we have as many color areas as we
  452.    * need
  453.    */
  454.  
  455.   while (allocated < n) {
  456.  
  457.     /* if our largest area can't be broken down, we can't even get the
  458.      * number of colors they asked us to
  459.      */
  460.  
  461.     if (largest_area->num_pixels < 2)
  462.       break;
  463.  
  464.     /* find midpoint of largest area and do split
  465.      */
  466.  
  467.     qsort(largest_area->pixels, largest_area->num_pixels, sizeof(short),
  468.       largest_area->sort_func);
  469.     count= 0;
  470.     midpoint= largest_area->pixel_count / 2;
  471.     for (x= 0; x < largest_area->num_pixels; x++) {
  472.       count += pixel_counts[largest_area->pixels[x]];
  473.       if (count > midpoint)
  474.     break;
  475.     }
  476.     if (x == 0) /* degenerate case; divide in half */
  477.       x= 1;
  478.     new_area= areas + allocated;
  479.     new_area->pixels= largest_area->pixels + x;
  480.     new_area->num_pixels= largest_area->num_pixels - x;
  481.     largest_area->num_pixels= x;
  482.     old_area= largest_area;
  483.     largest_area= largest_area->next;
  484.     if (largest_area)
  485.       largest_area->prev= (struct color_area *)NULL;
  486.     else
  487.       smallest_area= (struct color_area *)NULL;
  488.  
  489.     /* recalculate for each area of split and insert in the area list
  490.      */
  491.  
  492.     insertColorArea(pixel_counts, &largest_area, &smallest_area, old_area);
  493.     insertColorArea(pixel_counts, &largest_area, &smallest_area, new_area);
  494.  
  495.     allocated++;
  496.   }
  497.  
  498.   /* get destination image
  499.    */
  500.  
  501.   depth= colorsToDepth(n);
  502.   new_image= newRGBImage(image->width, image->height, depth);
  503.   sprintf(buf, "%s (%d colors)", image->title, n);
  504.   new_image->title= dupString(buf);
  505.  
  506.   /* calculate RGB table from each color area.  this should really calculate
  507.    * a new color by weighting the intensities by the number of pixels, but
  508.    * it's a pain to scale so this just averages all the intensities.  it
  509.    * works pretty well regardless.
  510.    */
  511.  
  512.   for (x= 0; x < allocated; x++) {
  513.     long red, green, blue, count, pixel;
  514.  
  515.     red= green= blue= 0;
  516.     count= areas[x].pixel_count;
  517.     for (y= 0; y < areas[x].num_pixels; y++) {
  518.       pixel= areas[x].pixels[y];
  519.       red += RED_INTENSITY(pixel);
  520.       green += GREEN_INTENSITY(pixel);
  521.       blue += BLUE_INTENSITY(pixel);
  522.       pixel_counts[pixel]= x;
  523.     }
  524.     red /= areas[x].num_pixels;
  525.     green /= areas[x].num_pixels;
  526.     blue /= areas[x].num_pixels;
  527.     new_image->rgb.red[x]= (unsigned short)(red << 11);
  528.     new_image->rgb.green[x]= (unsigned short)(green << 11);
  529.     new_image->rgb.blue[x]= (unsigned short)(blue << 11);
  530.   };
  531.   new_image->rgb.used= allocated;
  532.   new_image->rgb.compressed= 1;
  533.  
  534.   lfree(areas);
  535.  
  536.   /* copy old image into new image
  537.    */
  538.  
  539.   pixel= image->data;
  540.   dpixel= new_image->data;
  541.  
  542.   switch(image->type) {
  543.   case IRGB:
  544.     for (y= 0; y < image->height; y++)
  545.       for (x= 0; x < image->width; x++) {
  546.     valToMem(pixel_counts[TLA_TO_15BIT(image->rgb,
  547.                        memToVal(pixel, image->pixlen))],
  548.          dpixel, new_image->pixlen);
  549.     pixel += image->pixlen;
  550.     dpixel += new_image->pixlen;
  551.       }
  552.     break;
  553.  
  554.   case ITRUE:
  555.     for (y= 0; y < image->height; y++)
  556.       for (x= 0; x < image->width; x++) {
  557.     valToMem(pixel_counts[TRUE_TO_15BIT(memToVal(pixel, 3))],
  558.          dpixel, new_image->pixlen);
  559.     pixel += 3;
  560.     dpixel += new_image->pixlen;
  561.       }
  562.     break;
  563.   }
  564.   if (verbose)
  565.     printf("done\n");
  566.   return(new_image);
  567. }
  568.  
  569. /* expand an image into a true color image
  570.  */
  571.  
  572. Image *expand(image)
  573.      Image *image;
  574. {
  575.   Image *new_image;
  576.   int x, y;
  577.   Pixel spixval;
  578.   byte *spixel, *dpixel, *line;
  579.   unsigned int linelen;
  580.   byte mask;
  581.  
  582.   goodImage(image, "expand");
  583.   if TRUEP(image)
  584.     return(image);
  585.  
  586.   new_image= newTrueImage(image->width, image->height);
  587.   new_image->title= dupString(image->title);
  588.  
  589.   switch (image->type) {
  590.   case IBITMAP:
  591.     line= image->data;
  592.     dpixel= new_image->data;
  593.     linelen= (image->width / 8) + (image->width % 8 ? 1 : 0);
  594.     for (y= 0; y < image->height; y++) {
  595.       spixel= line;
  596.       mask= 0x80;
  597.       for (x= 0; x < image->width; x++) {
  598.     valToMem((mask & *spixel ? 0L : 0xffffff), dpixel, 3);
  599.     mask >>= 1;
  600.     if (!mask) {
  601.       mask= 0x80;
  602.       spixel++;
  603.     }
  604.     dpixel += new_image->pixlen;
  605.       }
  606.       line += linelen;
  607.     }
  608.     break;
  609.   case IRGB:
  610.      spixel= image->data;
  611.      dpixel= new_image->data;
  612.     for (y= 0; y < image->height; y++)
  613.       for (x= 0; x < image->width; x++) {
  614.     spixval= memToVal(spixel, image->pixlen);
  615.     valToMem(RGB_TO_TRUE(image->rgb.red[spixval],
  616.                  image->rgb.green[spixval],
  617.                  image->rgb.blue[spixval]),
  618.          dpixel, new_image->pixlen);
  619.     spixel += image->pixlen;
  620.     dpixel += new_image->pixlen;
  621.       }
  622.     break;
  623.   }
  624.   return(new_image);
  625. }
  626.